/**
 * 
 */
package leetCode;

import java.util.ArrayList;

/**
 * @author zhong
 *
 */
public class IncreasingOrderSearchTree {
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	ArrayList<Integer> arrayList = new ArrayList<>();

	public TreeNode increasingBST(TreeNode root) {
		traverse(root);
		root = null;
		// 根据得到的list重新构建树
		return contractTree();
	}

	private TreeNode contractTree() {
		if (arrayList.isEmpty()) {
			return null;
		}
		TreeNode root = new TreeNode(arrayList.get(0));
		TreeNode cur = root;
		for (int i = 1; i < arrayList.size(); i++) {
			cur.right = new TreeNode(arrayList.get(i));
			cur = cur.right;
		}
		return root;
	}

	private void traverse(TreeNode root) {
		if (root == null) {
			return;
		}
		traverse(root.left);
		arrayList.add(root.val);
		traverse(root.right);
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
